package queue;


import java.util.*;

/**
 * 数据流中的第 K 大元素
 */
public class KthLargestElementInAStream {
  public static void main(String[] args) {
    int[] nums = {};
    KthLargest kthLargest = new KthLargest(1, nums);
    System.out.println(kthLargest.add(-3));// return -3
    System.out.println(kthLargest.add(-2));// return -2
    System.out.println(kthLargest.add(-4));// return -2
    System.out.println(kthLargest.add(0));// return 0
    System.out.println(kthLargest.add(4));// return 4
  }

  /**
   * 使用堆PriorityQueue
   */
  static class KthLargest1 {

    final PriorityQueue<Integer> priorityQueue;
    final private int capacity;

    public KthLargest1(int k, int[] nums) {
      capacity = k;
      priorityQueue = new PriorityQueue<>(k);
      for (int i : nums) {
        this.add(i);
      }

    }

    public int add(int val) {
      //当queue中的元素少于capacity时，直接放入，返回堆顶元素
      if (priorityQueue.size() < capacity) {
        priorityQueue.offer(val);
        return priorityQueue.peek();
      } else {
        if (val > priorityQueue.peek()) {
          priorityQueue.poll();
          priorityQueue.offer(val);
        }
        return priorityQueue.peek();
      }
    }
  }


}

class KthLargest {

  private List<Integer> list;
  private int k;

  public KthLargest(int k, int[] nums) {
    this.k = k;
    list = new ArrayList<>(k);
    for (int i : nums) {
      this.add(i);
    }
  }

  public int add(int val) {
    list.add(val);
    Object[] tmp = list.toArray();
    Integer[] nums = new Integer[tmp.length];
    for (int i = 0; i < tmp.length; ++i) {
      nums[i] = (Integer) tmp[i];
    }
    Arrays.sort(nums, (o1, o2) -> o2 - o1);
    Integer ans = (list.size() < k) ? nums[0] : nums[k - 1];
    //注意，这里返回的List是：java.util.Arrays.ArrayList
    //而我们经常使用的ArrayList是java.util.ArrayList，这两者的用法有些不同
    List<Integer> tmpList = Arrays.asList(nums);
    List<Integer> transferList = new ArrayList<>(tmpList);
    list = transferList;
    return ans;
  }
}

